/*
现未使用该代码
*/

#include "global.h"
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int st[MAX_TAG_NUM],ed[MAX_TAG_NUM];
int i;

void Swap_unit(int i,int j1,int j2){
    int id1=disk[i][j1],id2=disk[i][j2];
    int k1=((i==object[id1].replica[1])?1:((i==object[id1].replica[2])?2:3));
    int k2=((i==object[id2].replica[1])?1:((i==object[id2].replica[2])?2:3));
    if(id1)
        object[id1].unit[k1][unit_num[i][j1]]=j2;
    if(id2)
        object[id2].unit[k2][unit_num[i][j2]]=j1;
    disk[i][j1]=id2;
    disk[i][j2]=id1;
    swap(unit_num[i][j1],unit_num[i][j2]);
}

void replaceCross(int i,vector<pair<int,int> >out[],priority_queue<int> q[],priority_queue<int>q0[][MAX_TAG_NUM]){
    for(int LEN=(M+1)/2;LEN>=1&&out[i].size()<K2;LEN--){
        for(int tag1=1;tag1<=M&&out[i].size()<K2;tag1++){
            int tag2=(tag1+LEN-1)%M+1;
            while(!q0[tag1][tag2].empty()&&!q0[tag2][tag1].empty()&&out[i].size()<K2){
                int j1;
                if(tag1&1)
                    j1=point_away(ed[tag1],q0[tag2][tag1].top());
                else
                    j1=point_away(st[tag1],-q0[tag2][tag1].top());
                assert(disk[i][j1]!=0);
                q0[tag2][tag1].pop();
                int j2;
                if(tag2&1)
                    j2=point_away(ed[tag2],q0[tag1][tag2].top());
                else
                    j2=point_away(st[tag2],-q0[tag1][tag2].top());
                assert(disk[i][j2]!=0);
                q0[tag1][tag2].pop();
                Swap_unit(i,j1,j2);
                out[i].push_back(make_pair(j1,j2));
            }
            while(!q0[tag2][tag1].empty()){
                q[tag1].push(q0[tag2][tag1].top());
                q0[tag2][tag1].pop();
            }
            while(!q0[tag1][tag2].empty()){
                q[tag2].push(q0[tag1][tag2].top());
                q0[tag1][tag2].pop();
            }
        }
    }

}

double calc(const int &a,const int &b){
    assert(a>0);assert(a<=M);
    assert(b>0);assert(b<=M);
    int sa=10,sb=10;
    int tlen=1800;
    sa+=get_num_read(vtag[a],timestamp+1,timestamp+tlen);
    sb+=get_num_read(vtag[b],timestamp+1,timestamp+tlen);
    return 1.0/sa*sb;
}
struct cmp{
    bool operator()(const pair<int,int>&a,const pair<int,int>&b) const{
        int ja1=a.first,taga2=a.second;
        if(taga2&1)
            ja1=point_away(ed[taga2],ja1);
        else
            ja1=point_away(st[taga2],-ja1);
        int taga1=object[disk[i][ja1]].tag;
        int jb1=b.first,tagb2=b.second;
        if(tagb2&1)
            jb1=point_away(ed[tagb2],jb1);
        else
            jb1=point_away(st[tagb2],-jb1);
        int tagb1=object[disk[i][jb1]].tag;
        return calc(taga1,taga2)<calc(tagb1,tagb2);
    }
};
struct cmp2{
    bool operator()(const pair<int,int>&a,const pair<int,int>&b) const{
        int ja1=a.first,taga2=a.second;
        if(taga2&1)
            ja1=point_away(ed[taga2],ja1);
        else
            ja1=point_away(st[taga2],-ja1);
        int taga1=object[disk[i][ja1]].tag;
        int jb1=b.first,tagb2=b.second;
        if(tagb2&1)
            jb1=point_away(ed[tagb2],jb1);
        else
            jb1=point_away(st[tagb2],-jb1);
        int tagb1=object[disk[i][jb1]].tag;
        return calc(taga1,taga2)>calc(tagb1,tagb2);
    }
};

void replaceSpace(int i,vector<pair<int,int> >out[],priority_queue<int>q[],priority_queue<int,vector<int>,greater<int> >space1[],priority_queue<int>space2[]){
    priority_queue<pair<int,int>,vector<pair<int,int> >,cmp>qall;
    for(int tag=1; tag<=M; tag++){

        if(((tag&1)&&space1[tag].empty())||(!(tag&1)&&space2[tag].empty())||q[tag].empty()) continue;
        int j;
        if(tag&1)
            j=point_away(ed[tag],q[tag].top());
        else
            j=point_away(st[tag],-q[tag].top());
        assert(disk[i][j]!=0);
        // if(tag&1)
            qall.push(make_pair(q[tag].top(),tag));
        q[tag].pop();
    }
    while(out[i].size()<K2){
        if(qall.empty()) break;
        auto tmp=qall.top();
        qall.pop();

        int tag=tmp.second;
        int j;
        if(tag&1)
            j=point_away(ed[tag],tmp.first);
        else
            j=point_away(st[tag],-tmp.first);
        
        int k=((tag&1)?space1[tag].top():space2[tag].top());
        (tag&1)?space1[tag].pop():space2[tag].pop();
        out[i].push_back(make_pair(j,k));
        Swap_unit(i,j,k);
        int tg = upper_bound(st+1,st+M+1,j) - st - 1;
        
        if(((tag&1)?space1[tag].size():space2[tag].size())&&!q[tag].empty()){
            qall.push(make_pair(q[tag].top(),tag));
            q[tag].pop();
        }
        if(ed[tg]>=j&&j>=st[tg]){
            assert(disk[i][j]==0);
            (tg&1)?space1[tg].push(j):space2[tg].push(j);
            if(((tg&1)?space1[tg].size():space2[tg].size())==1&&!q[tg].empty()){
                qall.push(make_pair(q[tg].top(),tg));
                q[tg].pop();
            }
        }
    }
}

void replaceItems(int i,vector<pair<int,int> >out[],priority_queue<int> q[]){
    priority_queue<pair<int,int>,vector<pair<int,int> >,cmp>q1[MAX_TAG_NUM],q2[MAX_TAG_NUM];
    priority_queue<pair<int,int>,vector<pair<int,int> >,cmp2>qs[MAX_TAG_NUM],qs2[MAX_TAG_NUM];
    priority_queue<pair<int,int>,vector<pair<int,int> >,cmp>qall;
    for(int tag=1;tag<=M;tag++){
        while(!q[tag].empty()){
            int j=q[tag].top();
            q[tag].pop();
            q1[tag].push(make_pair(j,tag));
            int jp;
            if(tag&1)
                jp=point_away(ed[tag],j);
            else
                jp=point_away(st[tag],-j);
            int tg=upper_bound(st+1,st+M+1,jp)-st-1;
            qs[tg].push(make_pair(j,tag));

        }
    }
    for(int tag=1; tag<=M; tag++){
        if(qs[tag].empty()||q1[tag].empty()) continue;
        qall.push(q1[tag].top());
        q1[tag].pop();
    }
    while(out[i].size()<K2){
        if(qall.empty()) break;
        auto tmp=qall.top();
        qall.pop();
        int tag=tmp.second;
        while(!qs2[tag].empty()&&qs[tag].top()==qs2[tag].top()){
            qs[tag].pop();
            qs2[tag].pop();
        }
        if(qs[tag].empty()) {
            q1[tag].push(tmp);
            continue;
        }
        if(!q2[tag].empty()&&q2[tag].top()==tmp){
            q2[tag].pop();
            while(!q2[tag].empty()&&q1[tag].top()==q2[tag].top()){
                q1[tag].pop();
                q2[tag].pop();
            }
            if(!q1[tag].empty()){
                qall.push(q1[tag].top());
                q1[tag].pop();
            }
            continue;
        }

        int j;
        if(tag&1)
            j=point_away(ed[tag],tmp.first);
        else
            j=point_away(st[tag],-tmp.first);

        pair<int,int>tmp2=qs[tag].top();
        qs[tag].pop();
        int tg=tmp2.second;
        int k;
        if(tg&1)
            k=point_away(ed[tg],tmp2.first);
        else
            k=point_away(st[tg],-tmp2.first);

        out[i].push_back(make_pair(j,k));
        Swap_unit(i,j,k);
        
        int tg2 = upper_bound(st+1,st+M+1,j) - st - 1;
        qs2[tg2].push(tmp);
        q2[tg].push(tmp2);
        if(tg&1)
            tmp2.first=(j-ed[tg]+V)%V;
        else
            tmp2.first=(st[tg]-j+V)%V;
        qs[tg2].push(tmp2);
        q1[tg].push(tmp);
        
        while(!qs2[tag].empty()&&qs[tag].top()==qs2[tag].top()){
            qs[tag].pop();
            qs2[tag].pop();
        }
        if(qs[tag].empty())
            continue;
        if(!q2[tag].empty()&&q2[tag].top()==tmp){
            q2[tag].pop();
            while(!q2[tag].empty()&&q1[tag].top()==q2[tag].top()){
                q1[tag].pop();
                q2[tag].pop();
            }
            if(!q1[tag].empty()){
                qall.push(q1[tag].top());
                q1[tag].pop();
            }
            continue;
        }
        
    }
}

void replaceInTag(int i,vector<pair<int,int> >out[],priority_queue<int,vector<int>,greater<int> >space1[],priority_queue<int>space2[]){
    int tagp[MAX_TAG_NUM];
    for(int i=1;i<=M;i++)
        tagp[i]=i;
    sort(tagp+1,tagp+M+1,[](int a,int b){
        double pw=1.0;
        double sa=0,sb=0,da=pow(100,pw),db=(100,pw);
        double tlen=1800;
        sa+=get_num_read(vtag[a],timestamp+1,timestamp+tlen);
        sb+=get_num_read(vtag[b],timestamp+1,timestamp+tlen);
        da+=pow(get_num_delete(vtag[a],timestamp+1,timestamp+tlen),pw);
        db+=pow(get_num_delete(vtag[b],timestamp+1,timestamp+tlen),pw);
        return sa/da>sb/db;
    });
    // for(int i=1;i<=M;i++)
    //     fprintf(stderr,"%d ",tagp[i]);
    // fprintf(stderr,"\n");
    for(int _=1;_<=M&&out[i].size()<K2;_++){
        int tag=tagp[_];
        int siz=0;
        for(int j=st[tag];j<=ed[tag];j++)
            if(disk[i][j])
                siz++;
        const double rate=1.0;
        const double kr=0.04;
        if(tag&1){
            for(int j=ed[tag];out[i].size()<K2&&!space1[tag].empty()&&space1[tag].top()<=st[tag]+siz*(rate+kr*_)&&j>st[tag]+siz*(rate+kr*_);j--){
                if(disk[i][j]){
                    int k=space1[tag].top();
                    space1[tag].pop();
                    out[i].push_back(make_pair(j,k));
                    Swap_unit(i,j,k);
                }
            }
        }
        else{
            for(int j=st[tag];out[i].size()<K2&&!space2[tag].empty()&&space2[tag].top()>=ed[tag]-siz*(rate+kr*_)&&j<ed[tag]-siz*(rate+kr*_);j++){
                if(disk[i][j]){
                    int k=space2[tag].top();
                    space2[tag].pop();
                    out[i].push_back(make_pair(j,k));
                    Swap_unit(i,j,k);
                }
            }
        }
    }
    for(int _=1;_<=M&&out[i].size()<K2;_++){
        int tag=tagp[_];
        int siz=0;
        for(int j=st[tag];j<=ed[tag];j++)
            if(disk[i][j])
                siz++;
        if(tag&1){
            for(int j=ed[tag];out[i].size()<K2&&!space1[tag].empty()&&space1[tag].top()<j&&j>=st[tag];j--){
                if(disk[i][j]){
                    int k=space1[tag].top();
                    space1[tag].pop();
                    out[i].push_back(make_pair(j,k));
                    Swap_unit(i,j,k);
                }
            }
        }
        else{
            for(int j=st[tag];out[i].size()<K2&&!space2[tag].empty()&&space2[tag].top()>j&&j<=ed[tag];j++){
                if(disk[i][j]){
                    int k=space2[tag].top();
                    space2[tag].pop();
                    out[i].push_back(make_pair(j,k));
                    Swap_unit(i,j,k);
                }
            }
        }
    }
}

void gbCollect2(){
    vector<pair<int,int> >out[MAX_DISK_NUM];
    // fprintf(stderr,"Garbage collection started\n");
    // fprintf(stderr,"Timestamp: %d\n",timestamp);
    for(i=1; i<=N; i++){
        priority_queue<int> q[MAX_TAG_NUM],q0[MAX_TAG_NUM][MAX_TAG_NUM];
        priority_queue<int,vector<int>,greater<int> >space1[MAX_TAG_NUM];
        priority_queue<int>space2[MAX_TAG_NUM];
        for(int tag=1; tag<=M; tag++){
            get_start_end(st[tag],ed[tag],tag);
        }
        for(int tag=1; tag<=M; tag++){
            for(int j=max(1,st[tag]);j<=ed[tag];j++){
                if(disk[i][j]==0){
                    if(tag&1)
                        space1[tag].push(j);
                    else space2[tag].push(j);
                }
                else if(object[disk[i][j]].tag!=tag){
                    assert(disk[i][j]!=0);
                    if(object[disk[i][j]].tag&1){
                        q0[tag][object[disk[i][j]].tag].push((j-ed[object[disk[i][j]].tag]+V)%V);
                    }
                    else{
                        q0[tag][object[disk[i][j]].tag].push((st[object[disk[i][j]].tag]-j+V)%V);
                    }
                }
            }
        }
        replaceCross(i,out,q,q0);
        replaceSpace(i,out,q,space1,space2);
        replaceItems(i,out,q);
        replaceInTag(i,out,space1,space2);
    }
    
    for(int i=1; i<=N; i++){
        fprintf(stderr,"%d ",(int) out[i].size());
        printf("%d\n",(int)out[i].size());
        for(auto x:out[i]) printf("%d %d\n",x.first,x.second);
    }
    fprintf(stderr,"\n");
    // fprintf(stderr,"Garbage collection finished\n");
    if(Round !=2) fflush(stdout);
}